#include "headfiles.h"

using namespace std;

// recursive
void preOrder(NODE *root);
void inOrder(NODE *root);
void postOrder(NODE *root);

// non-recursive
void preOrderNonRecur(NODE *root);
void inOrderNonRecur(NODE *root);
void postOrderNonRecur(NODE *root);

// level print
void levelOrder(NODE *root);

void printBinaryTree(NODE *root) {
	cout << "Pre-Order:" << endl;
	preOrder(root);

	cout << "\nPre-Order (non-recursive):" <<endl;
	preOrderNonRecur(root);
	
	cout << "\nIn-Order:" << endl;
	inOrder(root);

	cout << "\nIn-Order (non-recursive):" <<endl;
	inOrderNonRecur(root);
	
	cout << "\nPost-Order:" << endl;
	postOrder(root);

	cout << "\nPost-Order (non-recursive):" <<endl;
	postOrderNonRecur(root);

	cout << "\nLevel Order:" << endl;
	levelOrder(root);

	return;
}


void preOrder(NODE *root) {
	if (root == NULL) {
		return;
	}

	cout << root->i << endl;

	// left subtree
	preOrder(root->left);

	// right subtree
	preOrder(root->right);

	return;
}

void inOrder(NODE *root) {
	if (root == NULL) {
		return;
	}

	// left subtree
	inOrder(root->left);

	cout << root->i << endl;

	// right subtree
	inOrder(root->right);

	return;
}

void postOrder(NODE *root) {
	if (root == NULL) {
		return;
	}

	// left subtree
	postOrder(root->left);

	// right subtree
	postOrder(root->right);

	cout << root->i << endl;

	return;
}


void preOrderNonRecur(NODE *root) {
	if (root == NULL) {
		return;
	}

	stack<NODE *> node_stack;
	stack<int> count_stack;

	node_stack.push(root);	
	count_stack.push(0);

	while (!node_stack.empty()) {
		NODE *n = node_stack.top();
		int ref_count = count_stack.top();

		if (ref_count == 0) {
			cout << n->i << endl;
			
			// increase the ref count by 1
			count_stack.pop();
			count_stack.push(1);
			
			if (n->left) {
				node_stack.push(n->left);
				count_stack.push(0);
			}
		}
		// ref count is 2, add the right child
		else {
			node_stack.pop();
			count_stack.pop();
		
			if (n->right) {
				node_stack.push(n->right);
				count_stack.push(0);
			}
		}
	}
}

void inOrderNonRecur(NODE *root) {
	if (root == NULL) {
		return;
	}

	stack<NODE *> node_stack;
	stack<int> count_stack;

	node_stack.push(root);
	count_stack.push(0);
	while (!node_stack.empty()) {
		NODE *n = node_stack.top();
		int ref_count = count_stack.top();

		if (ref_count == 0) {
			count_stack.pop();
			count_stack.push(1);
			if (n->left) {
				node_stack.push(n->left);
				count_stack.push(0);
			}
		}
		// ref_count is 1, 
		else {
			// print out value
			cout << n->i << endl;
		
			// pop out the value
			count_stack.pop();
			node_stack.pop();
			
			// If there is right child, add to the stack
			if (n->right) {
				node_stack.push(n->right);
				count_stack.push(0);
			}
		}
	}

	return;
}

void postOrderNonRecur(NODE *root) {
	if (root == NULL) {
		return;
	}

	stack<NODE *> node_stack;
	stack<int> count_stack;

	node_stack.push(root);
	count_stack.push(0);

	while(!node_stack.empty()) {
		NODE *n = node_stack.top();
		int ref_count = count_stack.top();

		// First time accessed, left child is not traversed yet
		if (ref_count == 0) {
			// increase reference count by 1
			count_stack.pop();
			count_stack.push(1);

			// add left child if it has one
			if (n->left) {
				node_stack.push(n->left);
				count_stack.push(0);
			}
		}
		// Second time accessed, meaning left child is traversed
		// but right child not
		else if (ref_count == 1) {
			// incease the ref count from 1 to 2
			count_stack.pop();
			count_stack.push(2);
			
			// add right child if it hsa
			if (n->right) {
				node_stack.push(n->right);
				count_stack.push(0);
			}
		}
		// third time access, print out the value
		// and pop out the node
		else {
			cout << n->i << endl;
			node_stack.pop();
			count_stack.pop();
		}
	}

	return;
}


void levelOrder(NODE *root) {
	if (root == NULL) {
		return;
	}

	queue<NODE *> node_queue;
	node_queue.push(root);

	while (!node_queue.empty()) {
		NODE *n = node_queue.front();
		node_queue.pop();
		cout << n->i << endl;
		if (n->left) node_queue.push(n->left);
		if (n->right) node_queue.push(n->right);
	}

	return;
}


